Marbles

Memory limit: 128 MB

Byteted and Bited decided to play marbles. There is an ever number of marbles in the urn. Each marble has been marked by exactly one digit. The rules of the game are very simple: the players take on random one marble each from the urn in turns. The game ends when the urn is empty. The player who has accumulated a set of marbles with a larger product of digits, wins.

The boys very much got to like this game. They are both very ambitious and they really like to win, so a draw makes nobody happy. Byteted and Bited are determined to avoid such an ending situation at all costs. Write a program which will check if for a given initial set of marbles in the urn, the game can end up drawn.

Input

The first line of input contains one integer (), indicating the number of test cases to be considered.

Each of the following lines contains ten non-negative integers (), where indicates the number of marbles marked with digit. The sum of the numbers is even and positive in each test case.

Output

Your program should produce lines containing answers to respective test cases. The result for each test case that can end with a draw is word TAK (Polish for yes). In the opposite case the result should be NIE (Polish for no).

Example

For the input data:

5
0 1 0 1 1 4 1 0 5 1
0 1 1 0 3 0 0 0 0 3
1 1 0 4 0 0 2 0 0 2
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 999999 999999 1000000 1000000 1000000 1000000 1000000 1000000 1000000

the correct result is:

TAK
NIE
NIE
TAK
NIE

Task author: Jakub Radoszewski